#include<stdio.h>
int main()
{
	int a,b;
	int i,j,n;
	scanf("%d",&n);getchar();
	while(n--)
	{
		scanf("%d%d",&a,&b);
		a%=1000;
		j=a;
		for(i=1;i<b;i++)
		{
			a*=j;
			a%=1000;
		}
			printf("%d\n",a);
		/*if(a>=100)
			printf("%d\n",a);
		else if(10<=a&&a<100)
			printf("0%d\n",a);
		else
			printf("00%d\n",a);*/
	}
	return 0;
}
